import random
import itertools

def quicksort(input):
    """Performs an in-place quicksort."""
    if len(input) <= 1:
        return input
    leftPivot, rightPivot = partition(input)
    quicksort(itertools.islice(input, 0, leftPivot))
    quicksort(itertools.islice(input, rightPivot+1, len(input)))
    return input

def partition(input):
    pivotVal = input[0]
    leftPivot = rightPivot = 0

    left = 0
    right = len(input) - 1

    # we're maintaining the list in the format
    # [ only items < pivotVal ... only items = pivotVal ... unsorted items]
    
    while input[right] > pivotVal:
        right -= 1

    while left < leftPivot or right > rightPivot:

        if input[left] > pivotVal and input[right] < pivotVal:
            _swap(input,left,right)
        elif input[left] == pivotVal and input[right] < pivotVal:
            _swap(input, left, right)
            _swap(input, rightPivot + 1, right)
            leftPivot += 1
            rightPivot += 1
        elif input[left] > pivotVal and input[right] == pivotVal:
            _swap(input, left, right)
            _swap(input, left, leftPivot - 1)
            leftPivot -= 1
        elif input[left] == pivotVal and input[right] == pivotVal:
            _swap(input, right, rightPivot + 1)
            rightPivot += 1

        while input[left] < pivotVal:
            left += 1
        while input[right] > pivotVal:
            right -= 1

    return leftPivot, rightPivot
   
def _swap(list, i, j):
    tmp = list[i]
    list[i] = list[j]
    list[j] = tmp


if __name__ == "__main__":
    randList = [random.randrange(0,1000) for _ in range(1000)]
    print(randList)
    print()
    print(quicksort(randList))
    